package com.leetcode.根据数据结构分类.数组;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: ZhouBert
 * @date: 2021/2/20
 * @description: 697. 数组的度
 * https://leetcode-cn.com/problems/degree-of-an-array/
 */
public class A_697_数组的度 {

	public static void main(String[] args) {
		A_697_数组的度 action = new A_697_数组的度();
		test1(action);
	}

	public static void test1(A_697_数组的度 action) {
		// 1
		int[] A = new int[]{1 };
		int res = action.findShortestSubArray(A);
		System.out.println("res = " + res);
	}

	 /**
	 * 这道题似乎都不需要使用滑动窗口
	 * 1.遍历一遍，记录每个元素出现的首位置，尾位置，以及频数；
	 * 2.
	 *
	 * @param nums
	 * @return
	 */
	public int findShortestSubArray(int[] nums) {

		HashMap<Integer, Integer> beginMap = new HashMap<>();
		HashMap<Integer, Integer> endMap = new HashMap<>();
		HashMap<Integer, Integer> countMap = new HashMap<>();
		int len = nums.length;
		//出现最多的 次数
		int maxCount = 1;
		for (int i = 0; i < len; i++) {
			if (beginMap.containsKey(nums[i])) {
				//已经出现过
				endMap.put(nums[i], i);
			} else {
				beginMap.put(nums[i], i);
				endMap.put(nums[i], i);
			}
			if (countMap.containsKey(nums[i])) {
				int count = countMap.get(nums[i]) + 1;
				maxCount = Math.max(count, maxCount);
				countMap.put(nums[i], count);
			} else {
				countMap.put(nums[i], 1);
			}
		}
		//遍历 countMap 中 等于 count 的
		int min = len;
		for (Map.Entry<Integer, Integer> item :
				countMap.entrySet()) {
			if (item.getValue() == maxCount) {
				//计算一下 min
				min = Math.min(min, endMap.get(item.getKey()) - beginMap.get(item.getKey()) + 1);
			}
		}
		return min;
	}


}
